40-组合总和 II

题目

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

注意：解集不能包含重复的组合。

解题思路

这题和上一题的区别在于，这题的数组中的元素是有重复的，整体思路和上一题一样，但是需要注意的是，因为数组中的元素是有重复的

import "sort"

// @lc code=start
func combinationSum2(candidates []int, target int) [][]int {
	res := [][]int{}
	path := []int{}

	var backtrack func(int, int)
	backtrack = func(target, start int) {
		if target < 0 {
			return
		}
		if target == 0 {
			temp := make([]int, len(path))
			copy(temp, path)
			res = append(res, temp)
			return
		}

		for i := start; i < len(candidates); i++ {
			// 剪枝
			// 因为 candidates 排序了，所以当前元素和前一个元素相同，就跳过
			if i > start && candidates[i] == candidates[i-1] {
				continue
			}
			path = append(path, candidates[i])
			backtrack(target-candidates[i], i+1)
			path = path[:len(path)-1]
		}
	}

	// 对 candidates 排序
	sort.Ints(candidates)
	backtrack(target, 0)

	return res
}

在解释为什么在 "组合总和 II" 这个问题中需要排序和判断当前元素与上一个元素是否重复之前，让我们先理解一下问题本身。

"组合总和 II" 要求找出所有可能的组合，这些组合中的数字来自于一个数组，并且他们的和等于一个特定的目标数值。不同于 "组合总和 I"，在这个问题中，数组中的每个数字在每个组合中只能使用一次，而且数组中可能包含重复的数字。

为什么需要排序：

便于剪枝：排序后，相同的数字会被排列在一起，这使得在递归过程中更容易判断和处理重复的情况。
提早终止递归：如果当前的数字加上路径中已有数字的和已经超过了目标数值，由于数组是排序的，后面的数字只会更大，因此可以立即终止这个分支的探索。

为什么判断当前元素与上一个元素是否重复：

避免重复的组合：如果不加这个判断，那么对于数组中有重复数字的情况，会生成重复的组合。例如，对于数组 [1,1,2,5] 和目标数 3，没有这个判断的话，我们会得到两个 [1,2] 的组合。
确保每个数字只用一次：这个条件也帮助我们确保每个数字在组合中只被使用一次。这是因为我们在递归时改变了起始索引，确保不会重新使用同一层级已经使用过的数字。

总之，排序和这个特定的剪枝条件是为了提高效率，避免不必要的计算，并且确保找到的组合是符合问题要求的。

题目​

解题思路​

题目

解题思路